package jpnms.src;

import org.junit.Test;

import java.util.*;
import java.util.List;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.function.Consumer;

public class Solution {
    // 215.第k最大值
    Random random = new Random();

    public static long FuncPowerX(int x, int n) {
        long res = 1;
        for (int i = 0; i < n; i++) {
            res *= x;
        }

        return res;
    }

    public static int FuncPowerX2(int x, int n) {
        if (n == 0) {
            return 1;
        }
        return FuncPowerX2(x, n - 1) * x;

    }

    //704.二分搜索-1
    public int search1(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    //704.二分搜索-2
    public int search2(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

    //35. 搜索插入位
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length]) return nums.length;
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            } else if (target == nums[mid]) {
                return mid;
            }
        }
        //未找到时，区域缩1，target大，则为left+1，target小，则为left 会将边界值更新
        return left;
    }

    //27.原地删除  快慢指针
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) return 0;
        int ix = 0;//慢指针
        //快指针开跑
        for (int old = 0; old < nums.length; old++) {

            if (nums[old] != val) {
                nums[ix] = nums[old];
                ix++;
            }
        }
        return ix;
    }

    // 283.移动0
    public void moveZeroes(int[] nums) {
        int ix = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[ix++] = nums[i];
            }
        }
        while (ix < nums.length) nums[ix++] = 0;
    }

    // 844.比较含退格符的字符串-栈方法
    public boolean backspaceCompare(String s, String t) {
        StringBuilder ssb = new StringBuilder();
        StringBuilder tsb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '#') {
                ssb.append(c);
            } else if (ssb.length() > 0) {
                ssb.deleteCharAt(ssb.length() - 1);
            }
        }
        for (char c : t.toCharArray()) {
            if (c != '#') {
                tsb.append(c);
            } else if (tsb.length() > 0) {
                tsb.deleteCharAt(tsb.length() - 1);
            }
        }
        return ssb.toString().equals(tsb.toString());
    }

    // 844.比较含退格符的字符串-双指针方法
    public boolean backspaceCompare2(String s, String t) {
        int c_s = 0, c_t = 0;
        //从尾部开始遍历
        int ix_s = s.length() - 1, ix_t = t.length() - 1;
        while (true) {
            //开始一次消除#
            for (; ix_s >= 0; ix_s--) {
                if (s.charAt(ix_s) == '#') c_s++;
                else {
                    if (c_s > 0) c_s--;
                    else break;
                }
            }

            for (; ix_t >= 0; ix_t--) {
                if (t.charAt(ix_t) == '#') c_t++;
                else {
                    if (c_t > 0) c_t--;
                    else break;
                }
            }
            //消除到头
            if (ix_t < 0 || ix_s < 0) break;
            //判等当前所指字符
            if (s.charAt(ix_s) != t.charAt(ix_t)) return false;
            ix_t--;
            ix_s--;
        }
        //全部删完，相等
        if (ix_t == -1 && ix_s == -1) return true;
        return false;
    }

    //977.有序数组的平方
    public int[] sortedSquares(int[] nums) {
        //头尾双指针
        int st = 0, ed = nums.length;
        int i = ed - 1;
        int[] resu = new int[ed--];
        //只需要从头尾开始判定大小，所以双指针，自增减
        while (i >= 0) {
            resu[i--] = nums[st] * nums[st] >= nums[ed] * nums[ed] ? nums[st] * nums[st++] : nums[ed] * nums[ed--];
        }
        return resu;
    }

    //209. 长度最小的子数组
    public int minSubArrayLen(int s, int[] nums) {
        int st = 0;
        int sum = 0;
        int len = 0;
        //从ed开始遍历
        for (int ed = 0; ed < nums.length; ed++) {
            sum += nums[ed];
            //满足条件时，记录len，st前进
            while (sum >= s) {
                len = len == 0 ? ed - st + 1 : Math.min(len, ed - st + 1);
                sum -= nums[st++];
            }
        }
        return len;
    }

    //59. 螺旋矩阵 II   循环不变量原则：
    public int[][] generateMatrix(int n) {
        int[][] mat = new int[n][n];
        int sx = 0, sy = 0;
        int val = 1;
        for (int loop = 0; loop < n / 2; loop++, sx++, sy++) {
            int i = sx, j = sy;

            for (; j < n - loop - 1; j++) mat[i][j] = val++;
            for (; i < n - loop - 1; i++) mat[i][j] = val++;
            for (; j > sy; j--) mat[i][j] = val++;
            for (; i > sx; i--) mat[i][j] = val++;
        }
        if (n % 2 == 1) mat[sx][sy] = val;
        return mat;
    }

    @Test
    public void test_generateMatrix() {
        int[][] ints = generateMatrix(3);
        for (int[] col : ints) {
            for (int val : col) {
                System.out.println(val);
            }
        }
        System.out.println(ints);
    }


    //203. 移除链表元素
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }

    public ListNode removeElements2(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }


    //707.设计链表,虚拟头节点的设计
    class MyLinkedList {
        int size;
        ListNode head;

        public MyLinkedList() {
            size = 0;
            head = new ListNode(0);
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode tmp = head;
            for (int i = 0; i <= index; i++) {
                tmp = tmp.next;
            }
            return tmp.val;
        }

        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        public void addAtIndex(int index, int val) {
            if (index > size) return;
            if (index < 0) index = 0;

            ListNode tmp = head;
            for (int i = 0; i < index; i++) {
                tmp = tmp.next;
            }
            tmp.next = new ListNode(val, tmp.next);
            size++;
        }

        public void deleteAtIndex(int index) {
            if (index >= 0 && index < size) {
                ListNode tmp = head;
                for (int i = 0; i < index; i++) {
                    tmp = tmp.next;
                }
                tmp.next = tmp.next.next;
                size--;
            }
            return;
        }

    }

    @Test
    public void testMyLinkedList() {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        System.out.println(myLinkedList.get(1));              // 返回 2
        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
        myLinkedList.get(1);              // 返回 3
    }

    //    206. 递归反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //206. 反转链表
    public ListNode reverseList2(ListNode head) {

        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;

        }
        return prev;

    }

    //虚拟头结点解决链表翻转
    public ListNode reverseList3(ListNode head) {

        ListNode dumpyHead = new ListNode(-1);
        ListNode curr = head;
//        listNode
        while (curr != null) {
            ListNode tmp = curr.next;
            curr.next = dumpyHead.next;
            dumpyHead.next = curr;
            curr = tmp;
        }
        return dumpyHead.next;

    }

    //24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode dumpyHead = new ListNode(-1);
        dumpyHead.next = head;
        ListNode curr = dumpyHead;
        while (curr.next != null && curr.next.next != null) {
            ListNode n1 = curr.next;
            ListNode n2 = curr.next.next;
            curr.next = n2;
            n1.next = n2.next;
            n2.next = n1;
            curr = n1;
        }
        return dumpyHead.next;
    }

    //24. 两两交换链表中的节点,递归
    public ListNode swapPairs2(ListNode head) {
        if (head == null && head.next == null) return head;
        ListNode newHead = head.next;
        head.next = swapPairs2(head.next.next);
        newHead.next = head;
        return newHead;
    }

    //19.删除链表的倒数第N个节点,虚拟头节点避免了头结点删除问题
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp = new ListNode(-1);
        tmp.next = head;
        ListNode left = tmp;
        ListNode right = tmp;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;
        return tmp.next;
    }


    //面试题 02.07. 链表相交 ，先遍历一遍
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int numa = 0, numb = 0;
        ListNode tmpa = headA, tmpb = headB;
        while (tmpa != null) {
            tmpa = tmpa.next;
            numa++;
        }
        while (tmpb != null) {
            tmpb = tmpb.next;
            numb++;
        }
        tmpa = headA;
        tmpb = headB;
        for (int x = numa - numb; x > 0; x--) tmpa = tmpa.next;
        for (int y = numb - numa; y > 0; y--) tmpb = tmpb.next;
        while (tmpa != tmpb) {
            tmpa = tmpa.next;
            tmpb = tmpb.next;
        }
        return tmpb;
    }

    //142. 环形链表 II    快慢指针
    public ListNode detectCycle(ListNode head) {
        //双倍速快指针，同时开跑相遇在环内，距离入环z
        // 即2*(x+y)=n(y+z)+x+y ==>  x=(n-1)(y+z)+z
        // 则再次从头和相遇点开跑，最终在环起点相遇
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                ListNode id1 = fast;
                ListNode id2 = head;
                while (id2 != id1) {
                    id2 = id2.next;
                    id1 = id1.next;
                }
                return id1;
            }
        }
        return null;
    }

    //242.有效的字母异位词
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        if (s.length() == 0) return true;
        int[] tmp = new int[26];
        for (int i = 0; i < s.length(); i++) {
            tmp[s.charAt(i) - 'a'] += 1;
        }
        for (int i = 0; i < t.length(); i++) {
            tmp[t.charAt(i) - 'a'] -= 1;
        }

        for (int val : tmp) {
            if (val == 0) continue;
            return false;
        }
        return true;
    }

    @Test
    public void testIsAnagram() {
        String s = "wang";
        String t = "ngwa";
        boolean anagram = isAnagram(s, t);
        System.out.println(anagram);
    }

    //349. 两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        //方法1：将结果集合转为数组
        return resSet.stream().mapToInt(x -> (int) x).toArray();

        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
//        int[] arr = new int[resSet.size()];
//        int j = 0;
//        for(int i : resSet){
//            arr[j++] = i;
//        }
//
//        return arr;
    }

    //202. 快乐数
    public boolean isHappy(int n) {
        HashSet<Object> hset = new HashSet<>();
        while (n != 1 && !hset.contains(n)) {
            hset.add(n);
            n = getNextNub(n);
        }
        return n == 1;
    }

    private int getNextNub(int n) {
        int res = 0;
        while (n > 0) {
            int tmp = n % 10;
            res += tmp * tmp;
            n /= 10;
        }
        return res;
    }

    //1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hmap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hmap.containsKey(target - nums[i])) {
                return new int[]{i, hmap.get(target - nums[i])};
            }
            hmap.put(nums[i], i);

        }
        return new int[0];
    }

    //454. 四数相加 II   分组+哈希表
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> hmap = new HashMap<>();
        int resu = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                hmap.put(a + b, hmap.getOrDefault(a + b, 0) + 1);
            }
        }
        for (int c : nums3) {
            for (int d : nums4) {
                Integer val = hmap.getOrDefault(-(c + d), 0);
                resu += val;
            }
        }
        return resu;
    }

    //383. 赎金信   判断字符构成，键值对少用数组更快
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) return false;
        int[] record = new int[26];
        for (char c : magazine.toCharArray()) record[c - 'a']++;
        for (char c : ransomNote.toCharArray()) {
            record[c - 'a']--;
            if (record[c - 'a'] < 0) return false;
        }
        return true;
    }

    //15. 三数之和  a+b+c
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //排序后第一个大于0，直接返回结果
            if (nums[i] > 0) return result;
            //去重a
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //开始双指针
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int tmp = nums[left] + nums[right] + nums[i];
                if (tmp > 0) right--;
                else if (tmp < 0) left++;
                else if (tmp == 0) {
                    result.add(Arrays.asList(nums[left], nums[right], nums[i]));
                    //对b，c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }

    //18 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) return result;
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            // 跳过与上一个重复的值
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 最大值小于target，最小值大于target
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) continue;
            for (int j = i + 1; j < length - 2; j++) {
                // 跳过与上一个重复的值
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                // 最大值小于target，最小值大于target
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) continue;
                int left = j + 1, right = length - 1;
                // 开始双指针
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) right--;
                    else if (sum < target) left++;
                    else if (sum == target) {
                        // 找到时，跳过下一个重复值
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    //344 反转字符串
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];//记得自加减
            s[right--] = tmp;
        }
    }

    //541. 反转字符串 II
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i += 2 * k) {
            int st = i;
            int res = s.length() - st;
            int ed = res < 2 * k ? (res >= k ? i + k - 1 : s.length() - 1) : i + k - 1;
            while (st < ed) {
                char tmp = ch[st];
                ch[st++] = ch[ed];//记得自加减
                ch[ed--] = tmp;
            }
        }
        return new String(ch);

    }

    //剑指 Offer 05. 替换空格
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            char space = ' ';
            sb.append(tmp == space ? "%20" : tmp);

        }
        return sb.toString();
    }

    //剑指 Offer 05. 替换空格双指针，先遍历空格，添加双倍空格，再双指针逆序遍历完成替换
    public String replaceSpace2(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("  ");
            }
        }
        int left = s.length() - 1;
        s += sb.toString();
        int right = s.length() - 1;
        char[] tmp = s.toCharArray();
        while (left >= 0) {
            if (tmp[left] == ' ') {
                tmp[right--] = '0';
                tmp[right--] = '2';
                tmp[right--] = '%';
                left--;
            } else tmp[right--] = tmp[left--];

        }
        return new String(tmp);
    }

    //151.翻转字符串里的单词
    public String reverseWords(String s) {

        String res = new String();
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            //找到word开头
            if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i - 1) == ' ')) {
                if (count != 0) res += ' ';
                //复制字符串
                for (int j = i; j < s.length() && s.charAt(j) != ' '; j++) {
                    res += s.charAt(j);
                }
                count++;
            }
        }
        System.out.println(count);
        return res;
    }

    //151.翻转字符串里的单词  高级
    public String reverseWords2(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }

    //剑指Offer58-II.左旋转字符串
    public String reverseLeftWords(String s, int n) {
        char[] chars = new char[n];
        char[] old = s.toCharArray();

        for (int i = 0; i < s.length(); i++) {
            //前n位复制，同时开始移动
            if (i < n) {
                chars[i] = old[i];
                //若超出长度，转为移动chars
                old[i] = i + n < s.length() ? old[i + n] : chars[i - (s.length() - n)];
            } else if (i < s.length() - n) {
                old[i] = i + n < s.length() ? old[i + n] : chars[i - (s.length() - n)];
            } else
                old[i] = chars[i - s.length() + n];
        }

        return new String(old);
    }

    //剑指Offer58-II.左旋转字符串  Java api
    public String reverseLeftWords2(String s, int n) {
        StringBuilder sb = new StringBuilder(s);
        reverseLeftWordsString(sb, 0, n - 1);
        reverseLeftWordsString(sb, n, sb.length() - 1);

        return sb.reverse().toString();
    }

    public void reverseLeftWordsString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    //28. 找出字符串中第一个匹配项的下标

    /**
     * kmp 算法：
     * 获取next序列,next[i]为子字符串next[0:i+1]，最大长度的相同前后缀
     * i，j开始遍历，每轮i自加，j不匹配则跳转，匹配则自加
     * 前缀表达式：记录下标i之前的字符串中，有多大长度的相同前缀后缀
     * <p>
     * 匹配与next构建一模一样，区别为next在逐步构建，匹配则可以匹配返回
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        /**
         * kmp字符匹配算法,适用超长字符串
         * JDK为 O(n*m)
         * return  haystack.indexOf(needle);
         */
        //获取next数组，确定跳转位置
        int[] kmpnext = kmpnext(needle);
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            //不能继续匹配时，j跳转到下一次匹配的地方
            while (j != 0 && haystack.charAt(i) != needle.charAt(j)) j = kmpnext[j - 1];
            //匹配到时，j++
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            if (j == needle.length()) return i - j + 1;
        }
        return -1;
    }

    public int[] kmpnext(String pattern) {
        int[] next = new int[pattern.length()];
        //i=1（指针），j=0(已经匹配数)开始遍历
        for (int i = 1, j = 0; i < next.length; i++) {
            //不匹配时，j需要跳转到上一个匹配位置next[j-1]，即当前长度的前后缀不匹配，跳转到上一个长度的匹配处
            //next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度，此刻已经匹配了next[j]个字符，继续循环判断
            //"acabcacaa"  j=3,i=8时，开始跳转到j=next[j-1]=1，即i此刻的前缀==后缀
            while (j != 0 && pattern.charAt(i) != pattern.charAt(j)) j = next[j - 1];
            //匹配到时，j++
            if (pattern.charAt(i) == pattern.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }


    int[] getNext(String s) {
        int[] next = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j > 0; j--) {
                if (s.substring(0, j).equals(s.substring(i - j + 1, i + 1))) {
                    next[i] = j;
                    break;
                }
            }
        }
        return next;
    }

    //459.重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        //s[i]=s[i+n]，则以n为周期
        //此外其next[-1]必然为最大，且len-next[-1]为n，验证n是否为因数
        int len = s.length();
        if (len < 2) return false;
        int[] nexts = new int[s.length()];
        for (int i = 1, j = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = nexts[j - 1];
            if (s.charAt(i) == s.charAt(j)) j++;
            nexts[i] = j;
        }
        System.out.println(Arrays.toString(nexts));

        return nexts[len - 1] > 0 && len % (len - (nexts[len - 1])) == 0;
    }


    public boolean repeatedSubstringPattern2(String s) {
        return (s + s).indexOf(s, 1) != s.length();
    }


    //27. 移除元素
    public int removeElement2(int[] nums, int val) {
        if (nums.length == 1) return nums[0] == val ? 0 : 1;
        int l = 0, r = nums.length - 1;
        int tmp;
        int len = nums.length;
        //保证l与r错开
        while (l <= r) {
            //左边找==val的，右边找不等于val
            while (l < nums.length && nums[l] != val) l++;
            while (r >= 0 && nums[r] == val) r--;
            //找到时交换
            if (l < r) {
                tmp = nums[l];
                nums[l++] = nums[r];
                nums[r--] = tmp;
            }
            //r 必定能够找到非val的字符，哪怕-1，找不到时定义len
            len = r + 1;
        }
        return len;
    }

    //977. 有序数组的平方
    public int[] sortedSquares2(int[] nums) {
        int l = 0, r = nums.length - 1;
        int[] resu = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            resu[i] = nums[l] * nums[l] <= nums[r] * nums[r] ? nums[r] * nums[r--] : nums[l] * nums[l++];
        }
        return resu;
    }

    //209. 长度最小的子数组  滑动窗口
    public int minSubArrayLen2(int target, int[] nums) {
        int resu = 0;
        int sum = 0;
        int st = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                //更新resu，
                resu = resu == 0 ? i - st + 1 : i - st + 1 > resu ? resu : i - st + 1;
                sum -= nums[st++];
            }
        }


        return resu;
    }

    //59. 螺旋矩阵 II
    public int[][] generateMatrix2(int n) {

        if (n == 1) return new int[][]{{1}};
        int[][] res = new int[n][n];
        int val = 1, p = 1;
        //以圈数开始
        while (p <= n >> 1) {
            int x = p - 1, y = p - 1;
            while (y < n - p) res[x][y++] = val++;
            while (x < n - p) res[x++][y] = val++;
            while (y >= p) res[x][y--] = val++;
            while (x >= p) res[x--][y] = val++;
            p++;
        }
        if (n % 2 == 1) res[p - 1][p - 1] = n * n;
        return res;
    }

    //232. 用栈实现队列,fifo
    class MyQueue {
        Stack queueOut;
        Stack queueIn;
        int size;

        public MyQueue() {
            this.queueIn = new Stack<>();
            this.queueOut = new Stack<>();
            this.size = 0;
        }

        public void push(int x) {
            while (!queueOut.empty()) queueIn.push(queueOut.pop());
            queueIn.push(x);
            size++;
        }

        public int pop() {
            //不为空且Out为空
            while (!queueIn.empty()) queueOut.push(queueIn.pop());
            int res = (int) queueOut.pop();
            size--;
            return res;
        }

        public int peek() {
            if (queueOut.empty()) {
                while (!queueIn.empty()) queueOut.push(queueIn.pop());

            }
            return (int) queueOut.peek();

        }

        public boolean empty() {
            return size == 0;
        }
    }


    //225. 用队列实现栈
    class MyStack {
        ArrayDeque<Integer> queue;
        int size = 0;

        public MyStack() {
            this.queue = new ArrayDeque();
            this.size = 0;

        }

        public void push(int x) {
            queue.offerLast(x);
            size++;
        }

        public int pop() {
            Integer last = queue.peekLast();
            if (last != null) {
                queue.pollLast();
                size--;
            }
            return last;


        }

        public int top() {
            return queue.peekLast();

        }

        public boolean empty() {
            return queue.isEmpty();

        }
    }

    class MyStackLinkedList {
        LinkedList<Integer> queue;

        public MyStackLinkedList() {
            this.queue = new LinkedList<Integer>();
        }

        public void push(int x) {
            queue.offer(x);

        }

        public int pop() {
            return (int) queue.pollLast();

        }

        public int top() {
            return (int) queue.peekLast();
        }

        public boolean empty() {
            return queue.isEmpty();
        }


    }


    //20.有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            if (tmp == '(' || tmp == '[' || tmp == '{') stack.push(tmp);
            else {
                if (stack.empty()) return false;
                char res = stack.pop();
                if (res == '(' && tmp == ')' || res == '[' && tmp == ']' || res == '{' && tmp == '}') continue;
                else return false;
            }
        }
        return stack.empty() ? true : false;
    }

    //1047. 删除字符串中的所有相邻重复项
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.empty() && stack.peek() == s.charAt(i)) stack.pop();
            else stack.push(s.charAt(i));
        }
        String resu = "";
        while (!stack.empty()) resu = stack.pop() + resu;
        return resu;
    }

    //1047. 删除字符串中的所有相邻重复项  list 替代 stack
    public String removeDuplicates2(String s) {
        if (s.length() < 2) return s;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == s.charAt(i)) sb.deleteCharAt(sb.length() - 1);
            else sb.append(s.charAt(i));
        }
        return sb.toString();
    }

    //150. 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            switch (tokens[i]) {
                case "+": {
                    int op1 = Integer.parseInt(stack.pop());
                    int op2 = Integer.parseInt(stack.pop());
                    stack.push(Integer.toString(op1 + op2));
                    continue;
                }
                case "-": {
                    int op1 = Integer.parseInt(stack.pop());
                    int op2 = Integer.parseInt(stack.pop());
                    stack.push(Integer.toString(op2 - op1));
                    continue;
                }
                case "*": {
                    int op1 = Integer.parseInt(stack.pop());
                    int op2 = Integer.parseInt(stack.pop());
                    stack.push(Integer.toString(op1 * op2));
                    continue;
                }
                case "/": {
                    int op1 = Integer.parseInt(stack.pop());
                    int op2 = Integer.parseInt(stack.pop());
                    stack.push(Integer.toString(op2 / op1));
                    continue;
                }
            }
            stack.push(tokens[i]);
        }
        return Integer.parseInt(stack.peek());
    }

    //239. 滑动窗口最大值
    public int[] maxSlidingWindow(int[] nums, int k) {

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //判断o1<o2
                return o1[1] != o2[1] ? o2[1] - o1[1] : o2[0] - o1[0];
            }
        });
        int[] resu = new int[nums.length + 1 - k];
        for (
                int i = 0;
                i < k; i++) {
            pq.add(new int[]{i, nums[i]});
        }
        resu[0] = pq.peek()[1];
        //j为左侧，i为右侧[j,i]
        for (int i = k, j = 1; i < nums.length; i++) {
            pq.offer(new int[]{i, nums[i]});
            while (pq.peek()[0] < j) pq.poll();
            resu[j++] = pq.peek()[1];
        }
        return resu;
    }

    public int[] maxSlidingWindow2(int[] nums, int k){
        return null;
    }
    @Test
    public void myTest1() {
        String s1="1",s2="2";
        System.out.println(Integer.parseInt(s1));
    }


    @Test
    public void myTest() {
        Consumer consumer = (str) -> System.out.println(str);
        char a = 'r';
        char b = 'h';
        a ^= b;
        System.out.println(a);
        b ^= a;
        System.out.println(b);
        a ^= b;
        System.out.println(a);
        return;
    }

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] a, int l, int r, int index) {
        //随机进行一次分区，返回找到的最大值
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            //？在q+1到r区间继续寻找，在l到q-1区间继续寻找
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }

    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        //i 指向左边的第一个小值，如果找到小值，与++i交换，将小值移动到左边
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        //结束后交换末尾值与i+1
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public TreeNode constructBinaryTree(final int[] arr) {
        //创建树节点列表
        List<TreeNode> treeNodeList = arr.length > 0 ? new ArrayList<>(arr.length) : null;
        TreeNode root = null;
        //输入数组转换为，二叉树节点列表
        for (int i = 0; i < arr.length; i++) {
            TreeNode node = null;
            if (arr[i] != -1) {
                node = new TreeNode(arr[i]);
            }
            //都放进List,确定root节点
            treeNodeList.add(node);
            if (0 == i) {
                root = node;
            }
        }
        // 遍历一遍，根据规则左右孩子赋值就可以了
        // 注意这里 结束规则是 i * 2 + 1 < arr.length，避免空指针
        // 为什么结束规则不能是i * 2 + 2 < arr.length呢?
        // 如果i * 2 + 2 < arr.length 是结束条件
        // 那么i * 2 + 1这个符合条件的节点就被忽略掉了
        // 例如[2,7,9,-1,1,9,6,-1,-1,10] 这样的一个二叉树,最后的10就会被忽略掉
        for (int i = 0; i * 2 + 1 < arr.length; i++) {
            TreeNode node = treeNodeList.get(i);
            if (node != null) {
                // 线性存储转连式存储关键逻辑
                node.left = treeNodeList.get(2 * i + 1);
                //  再次判断下 不忽略任何一个节点
                if (i * 2 + 2 < arr.length) node.right = treeNodeList.get(2 * i + 2);
            }
        }


        return root;
    }

    // 节点类
    static class TreeNode {

        //节点值
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    //146. LRU 缓存-1
    class LRUCache {
        private int cap;
        private Map<Integer, Integer> map = new LinkedHashMap<>();

        public LRUCache(int capacity) {
            this.cap = capacity;
        }

        public int get(int key) {
            if (map.keySet().contains(key)) {
                int value = map.get(key);
                map.remove(key);
                //查询后重新放在末尾
                map.put(key, value);
                return value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (map.keySet().contains(key)) {
                map.remove(key);
            } else if (map.size() == cap) {
                Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
                iterator.next();
                iterator.remove();
                //Integer firstKey = map.entrySet().iterator().next().getValue();
                //map.remove(firstKey);
            }
            map.put(key, value);
        }
    }

    //146. LRU 缓存-2
    class LRUCache_2 {
        int cap;
        LinkedHashMap<Integer, Integer> cache;

        public LRUCache_2(int capacity) {
            this.cap = capacity;
            cache = new LinkedHashMap<Integer, Integer>(cap, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
//                    return super.removeEldestEntry(eldest);
                    return cache.size() > capacity;
                }
            };
        }

        public int get(int key) {
            return cache.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            cache.put(key, value);
        }
    }


}